public class BestTime2BuyAndSellStockWithCoolDown {
    /**
     * 309. 买卖股票的最佳时机含冷冻期
     *
     * 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。
     *
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     *
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 示例 1:
     * 输入: prices = [1,2,3,0,2]
     * 输出: 3
     * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     *
     * 示例 2:
     * 输入: prices = [1]
     * 输出: 0
     *
     * 提示：
     *
     * 1 <= prices.length <= 5000
     * 0 <= prices[i] <= 1000
     */

    public static void main(String[] args) {

    }

    /**
     * 由于多了冷静期，这里一天分成了4个状态：买入、今天卖出、冷静期、保持卖出
     * 这类题目的要点还是在于把握住每天的状态和转化规律
     * 动态规划其实就是有限状态机
     *
     * 1. dp数组下标及含义：
     *      dp[i][0]: 第i天为买入状态的持有最大金额；
     *      dp[i][1]: 在第i天卖出持有最大金额；
     *      dp[i][2]: 第i天为冷冻期持有的最大金额；
     *      dp[i][3]: 第i天为保持卖出状态的持有最大金额；
     * 2.递推公式：
     *      dp[i][0] = max(dp[i-1][0], max(dp[i-1][2] - prices[i], dp[i-1][3] - prices[i])) 要么前一天就买入了，要么今天买入，今天买入分为昨天是冷静期、昨天是保持卖出两种状态。取最大值
     *      dp[i][1] = dp[i-1][0] + prices[i] 前一天买入，今天卖出
     *      dp[i][2] = dp[i-1][1]   冷静期啥也干不了
     *      dp[i][3] = max(dp[i-1][3], dp[i-1][2])  前一天就是卖出状态，或者前一天是冷静期
     */
    public int mySolution(int[] prices) {
        int[] dp = new int[4];
        dp[0] = -prices[0];

        for (int i = 1; i < prices.length; i++){
            int old0 = dp[0];
            int old1 = dp[1];
            dp[0] = Math.max(dp[0], Math.max(dp[2], dp[3]) - prices[i]);
            dp[3] = Math.max(dp[3], dp[2]);
            dp[1] = old0 + prices[i];
            dp[2] = old1;
        }

        // 一定是卖了最多次赚的多
        return Math.max(dp[1], Math.max(dp[2], dp[3]));
    }
}
